import java.util.*;

public class BinaryTree {
    public static class BTNode {
        BTNode left;
        BTNode right;
        int val;

        BTNode(int value) {
            this.val = value;
        }
    }

    private BTNode root;
// 检测值为value的元素是否存在
    public BTNode find(BTNode root, int val) {

        if(root==null) {
           return null;
        }
        if(root.val==val) {
            return root;
        }
        BTNode p1 = find(root.left,val);
        if(p1!=null) {
            return p1;
        }
        BTNode p2 = find(root.right,val);
        if(p2!=null) {
            return p2;
        }
        return null;
    }
  public void levelOrder1(BTNode root){
        //层序遍历
        if(root==null) {
            return;
        }
      Deque<BTNode> deque=new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            BTNode cur=deque.poll();
            System.out.println(cur.val);
            if(cur.right!=null) {
                deque.offer(cur.right);
            }
            if(cur.left!=null) {
                deque.offer(cur.left);
            }
        }
    }
    public List<List<Integer>> levelOrder(BTNode root) {
        List<List<Integer>> list=new LinkedList<>();
        if(root==null) {
            return list;
        }
        Deque<BTNode> deque=new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size=deque.size();
            List<Integer> list1=new LinkedList<>();
            while (size!=0){
            BTNode cur=deque.poll();
            list1.add(cur.val);
            if(cur.left!=null) {
                deque.offer(cur.left);
            }
            if(cur.right!=null) {
                deque.offer(cur.right);
            }
            size--;
            }
            list.add(list1);
        }
        return list;
    }
    public BTNode lowestCommonAncestor(BTNode root, BTNode p, BTNode q) {
//找到最近的祖先
        if(root==null) {
            return null;
        }
        Deque<BTNode> deque1=new ArrayDeque<>();
        deque1.offer(root);
        Deque<BTNode> deque2=new ArrayDeque<>();
        deque2.offer(root);
        //找q
        Boolean p1=func(root.left,p,deque1);
        //找p
        Boolean p2=func(root.right,q,deque2);
        return func1(deque1,deque2);


    }
    public BTNode func1(Deque<BTNode> stack1,Deque<BTNode> stack2) {
        int max=stack1.size();
        int min=stack2.size();
        int num=max-min;
        if(num<0) {
            Deque<BTNode> tmp=stack1;
            stack1=stack2;
            stack2=tmp;

        }
        while (max!=min) {
            max--;
            stack1.pop();
        }
        while (max!=0) {
            if(stack1.peek()==stack2.peek()) {
                return stack1.pop();
            }
            stack1.pop();
            stack2.pop();
        }
        return null;
    }
    public  boolean func(BTNode root, BTNode cur,Deque<BTNode> stack) {
        if(root==null) {
            return false;
        }
        stack.offer(root);
        if(root==cur) {
            return true;
        }
        if(func(root.left,cur,stack)) {
            return true;
        }
        if(func(root.right,cur,stack)) {
            return true;
        }
        stack.pop();
        return false;
    }

    static class Node {
        char val;
        Node left;
        Node right;
        public Node(char val) {
            this.val=val;
        }
    }
    static int i=0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
       BinaryTree binaryTree=new BinaryTree();
        System.out.println("123");
        System.out.println("123");

    }
    public static Node func(String str,Node root) {
        if(str.charAt(i)=='#') {
            i++;
            return null;
        }
        Node node=new Node(str.charAt(i));
        i++;
        node.left= func(str,root.left);
        node.right= func(str,root.right);
        return node;
    }
    public static void printf(Node root) {
        if(root==null) {
            return;
        }
        printf(root.left);
        System.out.println(root.val+" ");
        printf(root.right);
    }
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val) {
            this.val=val;
        }
    }
    public TreeNode lowestCommonAncestor1(
            TreeNode root, TreeNode p, TreeNode q) {
        //找出俩个结点最近的公共祖先结点
        if(root==null) return null;
        if(p==root||q==root) return root;
        TreeNode p1=lowestCommonAncestor1(root.left,p,q);
        TreeNode p2=lowestCommonAncestor1(root.right,p,q);
        if(p1!=null&&p2!=null) return  root;
        if(p1!=null) return p1;
        if(p2!=null) return p2;
        return null;
    }
    int i1=0;
  /*  public TreeNode buildTree(int[] preorder, int[] inorder) {
    //根据前序变量中序遍历构建二叉树
      return  func2(preorder,inorder,0,preorder.length-1);
    }
    public TreeNode func2(int[] preorder, int[] inorder,int left,int right) {
        //写一个找到第i个结点和函数
        if(left>right) {
            return null;
        }
        int index=func3(inorder,left,right,preorder[i]);
        TreeNode root=new TreeNode(inorder[index]);
        i++;
        root.left=func2(preorder,inorder,left,index-1);
        root.left=func2(preorder,inorder,index+1,right);
        return root;
    }
    public int func3(int[]array,int left,int right,int k) {
        for (int j = left; j <= right; j++) {
            if(array[j]==k) {
                return  i;
            }
        }
        return -1;
    }*/
    public String tree2str(TreeNode root) {
    //转字符串
        StringBuilder stringBuilder=new StringBuilder();
        func4(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void func4(TreeNode root,StringBuilder str) {
        if(root==null) {
            return;
        }
            str.append('(');
            str.append(root.val);
            if(root.left==null) {
                str.append("()");
            }
            func4(root.left,str);
            func4(root.right,str);
            str.append(')');
    }
/*    public TreeNode buildTree2(int[] perorder, int[] intorder) {
        //中后续还原二叉树
        return func5(perorder,intorder,0,perorder.length-1);
    }
    public TreeNode func5(int[] perorder, int[] intorder,int left,int right) {
        if(left>right) {
            return null;
        }
        TreeNode root=new TreeNode(perorder[i]);
        int index=func6(intorder,left,right,perorder[i]);
        i++;
        root.left = func5(perorder,intorder,left,index-1);
        root.right= func5(perorder,intorder,index+1,right);
        return root;
    }*/
    public int func6(int[] array,int left,int right,int k) {
        for (int j = left; j <=right ; j++) {
            if(array[i]==k) {
                return i;
            }
        }
        return -1;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new LinkedList<>();
        if(root==null) {
            return list;
        }
        Deque<TreeNode> deque=new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size=deque.size();
            List<Integer> list1=new LinkedList<>();
            while (size!=0){
                TreeNode cur=deque.poll();
                list1.add(cur.val);
                size--;
                if(cur.left!=null) {
                    deque.offer(cur.left);
                }
                if(cur.right!=null) {
                    deque.offer(cur.right);
                }


            }
            list.add(0,list1);
        }
        return list;
    }

    /**
     *
     * @param root
     * @return
     */
    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(Node root) {
        if(root==null) {
            return true;
        }
        Deque<Node> deque=new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            Node cur=deque.poll();
            if(cur==null) {
               break;
            }
            deque.offer(cur.left);
            deque.offer(cur.right);
        }
       while (!deque.isEmpty()){
            if(deque.poll()!=null) {
                return false;
            }
        }
        return true;
    }
   /* //前序非递归遍历
    public void preorderTraversal(TreeNode root) {
        if(root==null) {
            return;
        }
        TreeNode cur=root;
        Deque<TreeNode> deque=new ArrayDeque<>();
      while(cur!=null||!deque.isEmpty()){
        while (cur!=null ) {
            deque.push(cur);
            System.out.print(root.val+"");
            cur=cur.left;

        }
            TreeNode top=deque.pop();
            cur=top.right;
        }
    }*/
   //前序非递归遍历
   public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> list=new LinkedList<>();
       if(root==null) {
           return list;
       }
       TreeNode cur=root;
       Deque<TreeNode> deque=new ArrayDeque<>();
       while(cur!=null||!deque.isEmpty()){
           while (cur!=null ) {
               deque.push(cur);
              list.add(cur.val);
               cur=cur.left;

           }
           TreeNode top=deque.pop();
           cur=top.right;
       }
       return list;
   }
}